package com.sheng.leetcode.year2023.month12.day28;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/12/28
 * <p>
 * 2735. 收集巧克力<p>
 * <p>
 * 给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。<p>
 * 每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。<p>
 * 在一步操作中，你可以用成本 x 执行下述行为：<p>
 * 同时修改所有巧克力的类型，将巧克力的类型 i^th 修改为类型 ((i + 1) mod n)^th。<p>
 * 假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums = [20,1,15], x = 5<p>
 * 输出：13<p>
 * 解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。<p>
 * 接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。<p>
 * 然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。<p>
 * 因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums = [1,2,3], x = 4<p>
 * 输出：6<p>
 * 解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。<p>
 * <p>
 * 提示：<p>
 * 1 <= nums.length <= 1000<p>
 * 1 <= nums[i] <= 10^9<p>
 * 1 <= x <= 10^9<p>
 */
public class LeetCode2735 {

    @Test
    public void test01() {
        int[] nums = {20, 1, 15};
        int x = 5;
//        int[] nums = {1, 2, 3};
//        int x = 4;
        System.out.println(new Solution().minCost(nums, x));
    }
}

class Solution {
    public long minCost(int[] nums, int x) {
        // nums[i]：i 代表巧克力的类型，nums[i] 代表收集所需的价格
        // 消耗 x 成本执行一次操作，可将巧克力的类型 i^th 修改为类型 ((i + 1) mod n)^th
        int n = nums.length;
        int[][] f = new int[n][n];
        for (int i = 0; i < n; ++i) {
            f[i][0] = nums[i];
            for (int j = 1; j < n; ++j) {
                f[i][j] = Math.min(f[i][j - 1], nums[(i - j + n) % n]);
            }
        }
        long ans = 1L << 60;
        for (int j = 0; j < n; ++j) {
            long cost = 1L * x * j;
            for (int i = 0; i < n; ++i) {
                cost += f[i][j];
            }
            ans = Math.min(ans, cost);
        }
        return ans;
    }
}
